Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт
до лабораторної роботи №1
“Знаходження шляхів графа”
виконала
студентка ПМ-21
Львів 2007
Мета роботи: Навчитись знаходити шляхи графа .
Завдання:
Знайти число шляхів, які відповідають деякій трійці невідємних чисел для матриці суміжності
Програма:
# include <iostream.h>
# include <iomanip.h>
# include <conio.h>
void main (void)
{
int A[6][6]={1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,1,0,1};
int S[6][6]={1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,1,0,1};
int D[6][6]={1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,1,0,1};
int C[6][6];
int E[6][6];
int p=0,i=0,j=0,k=0;
for ( i=0; i<6; i++)
{
for ( j=0; j<6; j++)
{
cout<<A[i][j]<<" ";
p++;
}
if(p==6)
{
cout<<"\n";
p=0;
}
}
int a=0,b=0,g=0;
cout<<"Vvedit alfa= ";
cin>>a;
cout<<"Vvedit beta= ";
cin>>b;
cout<<"Vvedit hama= ";
cin>>g;
int B[6][6];
i=j=0;
int s=2;
if (a==0)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
B[i][j]=1;
}
if (a==1)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
B[i][j]=A[i][j];
}
if (b==0)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
E[i][j]=1;
}
if (b==1)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
E[i][j]=A[i][j];
}
if (g==0)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
C[i][j]=1;
}
if (g==1)
{
for (i=0;i<6;i=i+1)
for(j=0;j<6;j=j+1)
C[i][j]=A[i][j];
}
if ((a!=0) && (a!=1) )
{
while (s<=a)
{
for (i=0;i<6;i=i+1)
{
for(j=0;j<6;j=j+1)
{
B[i][j]=0;
for(k=0;k<6;k=k+1)
{
B[i][j]+=A[i][k]*A[k][j];
}
}
if ((i==5) && (j==6) && (k==6) )
{
s++;
for(int a=0;a<6;a++)
for(int b=0;b<6;b++)
A[a][b]=B[a][b];
}
}
}
}
int ss=2;
if ((g!=0) && (g!=1) )
{
while (ss<=g)
{
for (i=0;i<6;i=i+1)
{
for(j=0;j<6;j=j+1)
{
C[i][j]=0;
for(k=0;k<6;k=k+1)
{
C[i][j]+=S[i][k]*S[k][j];
}
}
if ((i==5) && (j==6) && (k==6) )
{
ss++;
for(int a=0;a<6;a++)
for(int b=0;b<6;b++)
S[a][b]=C[a][b];
}
}
}
}
int sss=2;
if ((b!=0) && (b!=1) )
{
while (sss<=b)
{
for (i=0;i<6;i=i+1)
{
for(j=0;j<6;j=j+1)
{
E[i][j]=0;
for(k=0;k<6;k=k+1)
{
E[i][j]+=D[i][k]*D[k][j];
}
}
if ((i==5) && (j==6) && (k==6) )
{
sss++;
for(int a=0;a<6;a++)
for(int b=0;b<6;b++)
D[a][b]=E[a][b];
}
}
}
}
for(i=0;i<6;i++)
for(j=0;j<6;j++)
E[i][j]=(i==j)?E[i][j]:0;
int R[6][6];
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
R[i][j]=0;
for(k=0;k<6;k++)
R[i][j]+=B[i][k]*C[k][j];
}
}
int REZ[6][6];
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
REZ[i][j]=0;
for(k=0;k<6;k++)
REZ[i][j]+=R[i][k]*E[k][j];
}
}
for (i=0; i<6; i++)
{
for ( j=0; j<6; j++)
{
cout<<REZ[i][j]<<" ";
p++;
}
if(p==6)
{
cout<<"\n";
p=0;
}
}
}
Результат:
Висновок: Я навчилась знаходити шляхи графа.
